package com.year_23.april;

import java.util.Arrays;

/**
 * @author: jsh
 * @create: 2023/4/23 20:17
 * @Description:    1105. 填充书架  https://leetcode.cn/problems/filling-bookcase-shelves/
 * @FileName: Day23
 * @History:
 * @自定义内容：
 */
public class Day23 {
    public static void main(String[] args) {
        int[][] arr = {{1,1},{2,3},{2,3},{1,1},{1,1},{1,1},{1,2}};
        int[][] arr2  = {{1,3},{2,4},{3,2}};
        int[][] arr3 = {{7,3},{8,7},{2,7},{2,5}};
        System.out.println(minHeightShelves2(arr3, 10));

    }
    public static int minHeightShelves(int[][] books, int shelfWidth) {
        int l = books.length;
        int[] dp = new int[l + 1];
        Arrays.fill(dp,1000000);
        dp[0] = 0;
        dp[1] = books[0][1];
        for (int i = 1; i < l; i++) {
            int max = books[i][1];
            int widths = 0;
            for (int j = i; j >= 0; j--) {
                if ((widths+=books[j][0]) <= shelfWidth){
                    max = Math.max(max, books[j][1]);
                    dp[i+1] = Math.min(dp[i+1], dp[j] + max);
                }
            }
        }

        return dp[l];
    }

    public static int minHeightShelves2(int[][] books, int shelfWidth){
        int length = books.length;
        int[] dp = new int[length+1];
        Arrays.fill(dp, 1000000);
        dp[0] = 0;
        for (int i = 0; i < length; i++) {
            int max = 0,width = 0;
            for (int j = i; j >=0; j--) {
                if ((width+=books[j][0]) > shelfWidth)
                    break;
                max = Math.max(max, books[j][1]);
                dp[i+1] = Math.min(dp[i+1], dp[j] + max );
            }
        }
        return dp[length];
    }

}
